package mao.leetcode.others;

public class Interview51 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] a = {4,5,6,7};
        solution.reversePairs(a);
    }
    static class Solution {

        public int reversePairs(int[] nums) {
            int[] temp = new int[nums.length];
            return helper(nums,temp,0,nums.length);
        }
        public int  helper(int[] nums,int[] temp,int start,int end){
            //划分数组里面只有一个数字
            int revP = 0;
            if(start+1==end){
                return revP;
            }
            int mid = start+(end-start)/2;
            revP+=helper(nums,temp,start,mid);
            revP+=helper(nums,temp,mid,end);
            int i=start,j=mid,k=start,tempRevP=0;
            while(i<mid || j<end){
                if( i!=mid && (j==end || nums[i]<=nums[j]) ){  //如果相等，那么应该是前面那个先
                    temp[k++]=nums[i++];
                    revP+=(j-mid);   // 前面的数组里面的数被放置，发现逆序。
                }else{
                    temp[k++]=nums[j++];
                    // revP+=i-start;
                }
            }
            System.arraycopy(temp,start,nums,start,end-start);
            return revP;
            // for(i=start;i<end;i++){
            //     nums[i]=temp[i];
            // }
        }
    }
}
